---
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
    jupytext_version: 1.10.3
kernelspec:
  display_name: Python 3 (ipykernel)
  language: python
  name: python3
---

+++ {"slideshow": {"slide_type": "slide"}}

# Improved Quadratic Equation Solver

+++ {"slideshow": {"slide_type": "-"}, "tags": ["remove-cell"]}

**CS1302 Introduction to Computer Programming**
___

+++ {"slideshow": {"slide_type": "subslide"}}

In this notebook, we will improve the quadratic equation solver in the previous lab using conditional executions.  
First of all, run the following to setup the environment.

```{code-cell} ipython3
---
slideshow:
  slide_type: skip
---
from ipywidgets import interact
import math
import numpy as np
```

+++ {"slideshow": {"slide_type": "subslide"}}

## Discriminant

+++ {"slideshow": {"slide_type": "fragment"}}

Recall that a quadratic equation is

$$
ax^2+bx+c=0
$$

where $a$, $b$, and $c$ are real-valued coefficients, and $x$ is the unknown variable.

+++

````{prf:definition} Discriminant

The disciminant of a quadratic equation is defined as

$$
\Delta := b^2 - 4ac.
$$ (discriminant)

````

+++

The discriminant $\Delta$ discriminates the roots $\frac{-b\pm \sqrt{\Delta}}{2a}$ of a quadratic equation:

+++ {"slideshow": {"slide_type": "fragment"}}

````{prf:proposition} 

The roots of a quadratic equation {eq}`quadratic` are the same (repeated) equal to $-\frac{b}{2a}$ when the discriminant is zero, i.e., $\Delta=0$.

````

+++ {"slideshow": {"slide_type": "subslide"}}

**Exercise** Complete the following function by assigning `roots` only one root when the discriminant is zero. E.g., if $(a,b,c)=(1,-2,1)$, then `roots` should be assigned the value `1.0` instead of `1.0, 1.0`.

```{code-cell} ipython3
---
deletable: false
nbgrader:
  cell_type: code
  checksum: ab6fbcdff876e3cfc8767e7377284ccb
  grade: false
  grade_id: zero_determininant
  locked: false
  schema_version: 3
  solution: true
  task: false
slideshow:
  slide_type: fragment
tags: [remove-output]
---
def get_roots(a, b, c):
    d = b ** 2 - 4 * a * c  # discriminant
    if math.isclose(d, 0):
        # YOUR CODE HERE
        raise NotImplementedError()
    return roots
```

+++ {"slideshow": {"slide_type": "fragment"}}

````{hint}

Consider using the [if statement](https://docs.python.org/3/reference/compound_stmts.html#if) as follows:

```Python
def get_roots(a, b, c):
    d = b ** 2 - 4 * a * c  # discriminant
    if math.isclose(d, 0):
        roots = ___  # repeated root
    else:
        d **= 0.5
        roots = ___, ___
    return roots
```

This is a solution template where `___` needs to be filled in with appropriate code. If you have a more efficient/simpler implementation, you need *not* follow the solution template. E.g., to challenge your understanding of short-circuit evaluation, you can write your solution using boolean operations without any if statement.

````

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: 16860060eb7229216c52e0e6c7e96484
  grade: true
  grade_id: test-zero_determinant
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [hide-input, remove-output]
---
# tests
def test_get_roots(roots, a, b, c):
    def mysort(c):
        return c.real, c.imag

    roots_ = get_roots(a, b, c)
    assert (
        hasattr(roots, "__len__")
        and np.isclose(
            sorted(list(roots), key=mysort), sorted(list(roots_), key=mysort)
        ).all()
        or roots == roots_ or np.isclose(roots, roots_)
    )


test_get_roots((-1.0, 0.0), 1, 1, 0)
test_get_roots(0.0, 1, 0, 0)
```

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: ea74289e50129048beb923088ce499c8
  grade: true
  grade_id: hidden_test-zero_determinant
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [remove-cell]
---
# hidden tests
```

+++ {"slideshow": {"slide_type": "fragment"}}

**Exercise** Why use `math.isclose(d, 0)` instead of `d == 0`?

+++ {"deletable": false, "nbgrader": {"cell_type": "markdown", "checksum": "12889805830e3af64988ae0de141f1b7", "grade": true, "grade_id": "isclose", "locked": false, "points": 1, "schema_version": 3, "solution": true, "task": false}, "slideshow": {"slide_type": "fragment"}}

YOUR ANSWER HERE

+++ {"slideshow": {"slide_type": "slide"}}

## Linear equation

+++ {"slideshow": {"slide_type": "fragment"}}

If $a=0$, the earlier formula for the roots are invalid due to division by zero. Nevertheless, the equation remains valid:

$$
bx + c=0.
$$

+++

**Exercise** Improve the function `get_roots` to return the root $-\frac{c}{b}$ when $a=0$.

```{code-cell} ipython3
---
deletable: false
nbgrader:
  cell_type: code
  checksum: 790fe0b27e9e6efe7e54afa74e32dbad
  grade: false
  grade_id: linear
  locked: false
  schema_version: 3
  solution: true
  task: false
tags: [remove-output]
---
def get_roots(a, b, c):
    d = b ** 2 - 4 * a * c
    # YOUR CODE HERE
    raise NotImplementedError()
    return roots
```

````{hint} 

Solution template:
```Python
def get_roots(a, b, c):
    d = b ** 2 - 4 * a * c    # discriminant
    if ___:
        roots = ___
    elif math.isclose(d, 0):
        roots = ___  # repeated root
    else:
        d **= 0.5
        roots = ___
    return roots
```

````

```{code-cell} ipython3
---
code_folding: []
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: 5c1bddf43ef773f22d90ffad549ccc45
  grade: true
  grade_id: test-linear
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [remove-output, hide-input]
---
# tests
test_get_roots((-1.0, -0.0), 1, 1, 0)
test_get_roots(0.0, 1, 0, 0)
test_get_roots(0.5, 0, -2, 1)
```

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: 0b77d8b49baaccd677119a45a0a2a230
  grade: true
  grade_id: hidden_test-linear
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [remove-cell]
---
# hidden tests
```

## Degenerate cases

+++

What if $a=b=0$? In that case, the equation becomes

$$
c = 0
$$
which is always satisfied if $c=0$ but never satisfied if $c\neq 0$. 

+++ {"slideshow": {"slide_type": "fragment"}}

**Exercise** Improve the function `get_roots` to return root(s) under all cases:
- If $a=0$ and $b\neq 0$, assign `roots` to the single root $-\frac{c}{b}$. 
- If $a=b=0$ and $c\neq 0$, assign `roots` to `None`.  
    Note that `None` is an object, not a string.
- If $a=b=c=0$, there are infinitely many roots. Assign to `roots` the tuple `-float('inf'), float('inf')`.  
    Note that `float('inf')` converts the string `'inf'` to a floating point value that represents $\infty$.

```{code-cell} ipython3
---
deletable: false
nbgrader:
  cell_type: code
  checksum: 474f601f43c279d150f959b1672c2f86
  grade: false
  grade_id: degenerate
  locked: false
  schema_version: 3
  solution: true
  task: false
slideshow:
  slide_type: skip
tags: [remove-output]
---
def get_roots(a, b, c):
    d = b ** 2 - 4 * a * c
    # YOUR CODE HERE
    raise NotImplementedError()
    return roots
```

+++ {"slideshow": {"slide_type": "fragment"}}

````{hint} 

Use nested `if` statements as in the solution template:

```Python
def get_roots(a, b, c):
    d = b**2 - 4 * a * c
    if ___:
        if ___:
            if ___:
                roots = -float('inf'), float('inf')
            else:
                roots = None
        else:
            ___
    elif math.isclose(d, 0):
        roots = ___  # repeated root
    else:
        d **= 0.5
        roots = ___
    return roots
```

````

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: 5d991e44c6b5378dbe741263bcf09984
  grade: true
  grade_id: test-degenerate
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
slideshow:
  slide_type: skip
tags: [hide-input, remove-output]
---
# tests
test_get_roots((-1.0, 0.0), 1, 1, 0)
test_get_roots(0.0, 1, 0, 0)
test_get_roots((-float('inf'), float('inf')), 0, 0, 0)
test_get_roots(None, 0, 0, 1)
test_get_roots(0.5, 0, -2, 1)
test_get_roots(1.0, 1, -2, 1)
```

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: 8ee8bbfeb16c1bf80e555537f093154d
  grade: true
  grade_id: test_test-degenerate
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [remove-cell]
---
# hidden tests
```

After you have complete the exercises, you can run your robust solver below:

```{code-cell} ipython3
---
code_folding: [0]
slideshow:
  slide_type: '-'
tags: [remove-output]
---
# quadratic equations solver
@interact(a=(-10,10,1),b=(-10,10,1),c=(-10,10,1))
def quadratic_equation_solver(a=1,b=2,c=1):
    print('Root(s):',get_roots(a,b,c))
```

## Flowcharts (optional)

+++

Let's play a game to test your understanding of boolean expressions. Run the following program and choose your input so that 1, 2, 3 are each printed in a separate line as follows:
``` 
1
2
3
```

```{code-cell} ipython3
:tags: [remove-output]

input(1) or input(2) and input(3)
```

````{hint}

The following flowchart describes the [short-circuit evaluation](https://docs.python.org/3/reference/expressions.html?highlight=precedence#boolean-operations) for the boolean expression as follows:

![1or2and3](images/1or2and3.svg)

````

+++

**How to read the flowchart?**

+++

A flowchart uses arrows to connects a set of [annotated blocks][bb]. The rules were first specified by ANSI and later adopted in [ISO 5807][iso].

[bb]: https://en.wikipedia.org/wiki/Flowchart#Building_blocks
[iso]: https://webstore.ansi.org/Standards/ISO/ISO58071985

+++

For the above game, start from the first decision block at the top and choose the input appropriately to transition along the `yes` arrows.

+++

**Why use a program flowchart?**

+++

A program flowchart is a powerful way of describing an algorithm quickly. Unlike a text-based programming language:
- The rules governing the program flow can be shown explicitly by arrows.
- The annotated graphical blocks can convey the meaning faster using visual clues. 

+++

A programmer can draft a program in flowchart without worrying about syntax (indentation, colon, ...). E.g., the above flow chart can be implemented as follows using the if statement instead of the boolean operators.

```{code-cell} ipython3
:tags: [remove-output]

if not input(1):
    if input(2):
        input(3)
```

**How to convert the program to a flowchart automatically?**

+++

To draw a flowchart, we can use a vector graphics editor. [Inkscape](https://inkscape.org/) is an open source software the runs in Linux/Mac/Windows. To run on mobile devices, you can run it with the desktop launcher in your jupyter server.

+++

A web application you can run without a desktop is [`ipydrawio`](https://ipydrawio.readthedocs.io/en/stable/):
- In the file tab, create a file called `test.dio.svg` and double click it.
- After you finished drawing the flowchart, save it and use it as an [SVG image](https://en.wikipedia.org/wiki/Scalable_Vector_Graphics).

+++

The most convenient way, of course, is to ask python to convert a python code to a flowchart automatically. This can be done with [`pyflowchart`](https://github.com/cdfmlr/pyflowchart):

```{code-cell} ipython3
from pyflowchart import Flowchart

def code2flow(code):
    '''
    Given input code (as a string), returns the flowchart (as a string) that can be rendered by
    http://flowchart.js.org
    '''
    return Flowchart.from_code(code, simplify=False).flowchart()
```

Pass the code as a string to `code2flow`:

```{code-cell} ipython3
fc = code2flow('''
if not input(1):
    if input(2):
        input(3)
''')
print(fc)
```

The output is a string in a [domain-specific language (DSL)][dsl] that can be [rendered here with flowchart.js][fc]. Simply overwrite a demo textbox there with the printed flowchart code above.

[dsl]: https://en.wikipedia.org/wiki/Domain-specific_language
[fc]: http://flowchart.js.org

+++

**How to write a documentation with flowcharts?  
What about other DSL for special contents such as diagrams, equations, lists, ...?**

+++

[Markdown](https://en.wikipedia.org/wiki/Markdown) is becoming popular in writing documentations. jupyter notebooks, jupyterbook, github, ... all supports markdown, but to different extents:

- Jupyter notebook such as this one supports [CommonMark](https://commonmark.org).
- Our [cs1302 jupyterbook](https://www.cs.cityu.edu.hk/~ccha23/cs1302book) is written in [MyST](https://myst-parser.readthedocs.io/en/latest/syntax/syntax.html) markdown.
- Github uses [Github Flavored Markdown (GFM).](https://github.github.com/gfm/)

Unfortunately, none of them support the flowchart code currently.

+++

Nevertheless, many editors such as [Typora](https://typora.io) supports advanced Markdown language with live preview. We can also extend VS Code to do the same using [Markdown Preview Enhanced](https://shd101wyy.github.io/markdown-preview-enhanced/#/) as follows:

+++

````{tip}

You can install any extension on the VS Code interface of the JupyterHub server. To render flowchart code:

1. Open `Launcher` (click on the **+** sign in the top left or press `Shift + Ctrl + L`) and click on `VS Code` to create a VSCode tab
2. Click the extension tab on the left and search for *Markdown Preview Enhanced*.
3. Click install and refresh the browser.
4. Click the file explorer tab and create a new file say `test.md` file.
5. Insert the flowchart in DSL to the `test.md` [as follows](https://shd101wyy.github.io/markdown-preview-enhanced/#/diagrams?id=flow-charts):  
    ````Markdown
    ```flow
    cond3=>condition: if (not input(1))
    cond8=>condition: if input(2)
    sub12=>subroutine: input(3)

    cond3(yes)->cond8
    cond8(yes)->sub12
    ```
    ````
6. To show the live preview, click the `open preview` button of Markdown Preview Enhanced located on the tool bar at the top right-hand corner.

You can also using `drawio` in VS Code using [the extension here](https://marketplace.visualstudio.com/items?itemName=hediet.vscode-drawio).

````

+++

Finally, note that the flow chart does not implement how short-circuit evaluation returns values. E.g., consider entering `a` for all the inputs and see the difference in the output of the boolean expression and the code that implements the flowchart.

```{code-cell} ipython3
:tags: [remove-output]

input(1) or input(2) and input(3)
```

```{code-cell} ipython3
:tags: [remove-output]

if not input(1):
    if input(2):
        input(3)
```

**Exercise** (Optional) Can you implement the boolean expression exactly with the same return value using only conditionals but not boolean operators?

+++

````{hint}

Consider using [conditional expression](https://docs.python.org/3/reference/expressions.html#conditional-expressions) and [assignment expression](https://docs.python.org/3/reference/expressions.html#grammar-token-assignment-expression).

````